package org.vsg.stock.core.algorithm;

import java.util.List;

public class ListQuickSort<S extends Sortable> extends AbstractSortCalculator {



	private static ListQuickSort listInst = null;

	public static ListQuickSort getInstance() {
		return getInstance(SortOrder.ASC);
	}

	public static ListQuickSort getInstance(
			AbstractSortCalculator.SortOrder sortOrder) {

		if (listInst == null) {
			listInst = new ListQuickSort();
		}
		listInst.setSortOrder(sortOrder);
		return listInst;
	}

	@Override
	public void calculate() {
		// --- when the size is '1' ---
		if ( this.getSortList().size() < 2 ) {
			return ;
		}
		changeMaxAndMinBorder();
		quicksort(0, this.getSortList().size() - 1);
	}
	
	
	private void changeMaxAndMinBorder() {
		List sortList = this.getSortList();
		int leastIndex = 0 ;
		double tmp = 0;
		for (int i = 0 ; i < sortList.size() ; i++) {
			int j = sortList.size() - 1 - i;
			if ( i == 0 ) {
				tmp = ((S)sortList.get(i)).getValue();
			}
			else {
				double current = ((S)sortList.get(i)).getValue();
				double currentMax = ((S)sortList.get(j)).getValue();
				if (  current < tmp) {
					leastIndex = i;
					tmp = current;
				}
			}
		}
		
		// --- swap other ----
		double leastIndexValue = ((S)sortList.get(leastIndex)).getValue();
		for (int i = 0 ; i < sortList.size() ; i++) {
			double current = ((S)sortList.get(i)).getValue();
			if (current == leastIndexValue) {
				continue;
			} else {
				swap(sortList , i , leastIndex);
				break;
			}
		}



		
	}

	private void quicksort(int left, int right) {
		int index = partition(left, right); 

		if ( left < index -1) {
			quicksort(left, index - 1);
		}
		if ( index < right ) {
			quicksort(index, right);
		}
		
		
	}
	
	private int partition(int left , int right) {

		int i = left, j = right;
		List sortList = this.getSortList();
		int middleIndex = (left + right) / 2 ;
		S pivot = (S)sortList.get( middleIndex );
		while (i < j) {
			S leftElem = null;
			int leftSwapIndex = 0;
			do {
				leftSwapIndex = i++;
				leftElem = (S)sortList.get(leftSwapIndex);
			} while (leftElem.getValue() < pivot.getValue());
			
			S rightElem = null;
			int rightSwapIndex = 0;
			do {
				rightSwapIndex = j--;
				rightElem = (S)sortList.get(rightSwapIndex);
			} while (rightElem.getValue() > pivot.getValue() );
			
			if ( leftSwapIndex == 8) {
				System.out.println("test");
			}
			
			if (leftSwapIndex <= rightSwapIndex) {
				// --- swap ---
				if (leftElem.getValue() == rightElem.getValue() ) {
					swap( sortList , leftSwapIndex, leftSwapIndex+1);
					i++;
				} else {
					swap( sortList , leftSwapIndex, rightSwapIndex);
				}
			}
			
		}
		
		return i;
	}

}
